207. 课程表

Similar Question

Solution Tips

方案一: Dfs

function initializeColor(vertices) {
  const color = []
  for (let i = 0; i < vertices.length; i++) {
      color[vertices[i]] = 'white' //{1} 
  }
  return color
}
var canFinish = function (numCourses, prerequisites) {
  if (numCourses <= 0) return false
  const len = prerequisites.length
  if (len === 0) return true

  const vertices = []
  const adjList = new Map()
  for (let i = 0; i < numCourses; i++) {
      vertices[i] = i
      adjList.set(i, [])
  }
  for (const p of prerequisites) {
      adjList.get(p[1]).push(p[0])
  }
  let color = initializeColor(vertices)
  // 因为此题并不需要排序，仅仅判断有无成环即可，所以无需维护栈
  for (let i = 0; i < vertices.length; i++) {
      if (dfsVisit(vertices[i], adjList, color)) {
          return false
      }
  }
  // 在遍历的过程中，一直 dfs 都没有遇到已经重复访问的结点，就表示有向图中没有环
  // 所有课程任务可以完成，应该返回 true
  return true

  function dfsVisit(v, adjList, color) {
      // 访问了正在访问的节点，成环，没必要继续递归了
      if (color[v] === 'grey') return true
      // 访问过的节点，说明有共同的后继点，但是不成环
      if (color[v] === 'black') return false

      // 表示正在访问中
      color[v] = 'grey'
      const predecessors = adjList.get(v)
      for (let i = 0; i < predecessors.length; i++) {
          const u = predecessors[i]
          // 层层递归返回 true ，表示图中存在环
          if (dfsVisit(u, adjList, color)) return true
      }
      // v 的所有后继点都访问完了，都没有存在环，则这个结点就可以被标记为已经访问结束
      color[v] = 'black'
      // false 表示图中不存在环
      return false
  }
}
let numCourses = 2, prerequisites = [[0, 1], [1, 0]]
console.log(canFinish(numCourses, prerequisites))

方案二: Kahn 算法 - 广度优先

var findOrder = function(numCourses, prerequisites) {
   if (numCourses <= 0) return []
   const len = prerequisites.length

   // 入度数组
   const requireCount = new Array(numCourses).fill(0)
   for (const p of prerequisites) {
       // course[0]对应的课程，需要前置课程，有入度
       requireCount[p[0]]++
   }

   // 构建邻接表
   const adjList = {};
   for(let i = 0; i < len; i++) {
       const v = prerequisites[i][1];
       const u = prerequisites[i][0];

       if (adjList[v]) {
           adjList[v].push(u);
       }
       else {
           adjList[v] = [u];
       }
   }

   const queue = [];
   // 首先加入入度为 0 的结点, 作为 bfs 的起点
   for (let i = 0; i < numCourses; i++) {
       if (requireCount[i] == 0) {
           queue.push(i);
       }
   }
   const res = []
       // 拓扑排序
   while (queue.length !== 0) {
       // 入度为 0 的删除
       const learned = queue.shift()
       res.push(learned)
       // 把邻边全部遍历一下
       const adjust = adjList[learned]
       if (adjust?.length > 0) {
           for(let i = 0; i < adjust.length; i++) {
               const u = adjust[i];
               requireCount[u]--
               if (requireCount[u] == 0) queue.push(u)
           }
       }
   }

   return res.length === numCourses ? res : []
};
let numCourses = 3, prerequisites = [[1, 0], [1, 2], [2, 1]]
console.log(canFinish(numCourses, prerequisites))